Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Holder constants

摘要

In this paper, the global optimization problem $\min_{y\in S} F(y)$ with $S$being a hyperinterval in $\Re^N$ and $F(y)$ satisfying the Lipschitz conditionwith an unknown Lipschitz constant is considered. It is supposed that thefunction $F(y)$ can be multiextremal, non-differentiable, and given as a`black-box'. To attack the problem, a new global optimization algorithm basedon the following two ideas is proposed and studied both theoretically andnumerically. First, the new algorithm uses numerical approximations tospace-filling curves to reduce the original Lipschitz multi-dimensional problemto a univariate one satisfying the H\"{o}lder condition. Second, the algorithmat each iteration applies a new geometric technique working with a number ofpossible H\"{o}lder constants chosen from a set of values varying from zero toinfinity showing so that ideas introduced in a popular DIRECT method can beused in the H\"{o}lder global optimization. Convergence conditions of theresulting deterministic global optimization method are established. Numericalexperiments carried out on several hundreds of test functions show quite apromising performance of the new algorithm in comparison with its directcompetitors.